package ACWing._3_完全背包;

import java.util.Scanner;

public class Main {
    static int[] dp = new int[1010];
    static int[] weights = new int[1010];
    static int[] values = new int[1010];
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();  // 物品数量
        int v = scanner.nextInt();  // 背包容量
        for (int i = 1; i <= n; i++) {
            weights[i] = scanner.nextInt();
            values[i] = scanner.nextInt();
        }
        // dp[i][j]： 0..i之间的物品任取放进容量为j的背包，的最大价值
        // 初始化
        for (int i = 1; i <= n; i++) {
            // 完全背包是 左->右
            for(int j = weights[i];j<=v ; j++){
                dp[j] = Math.max(dp[j], dp[j-weights[i]]+values[i]);
            }
        }
        System.out.println(dp[v]);
        scanner.close();
    }
}
